package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 找出一组数中的第k小元素
 * 
 * @author 付大石
 */
public class Main {

    public static void main(String[] args) {
        
        Integer[] arr = new Integer[] { 54, 23, 65, 12, 76, 34, 87 };
//      sort(arr); //校验切分是否写对了
//      System.out.println(Arrays.toString(arr));
        System.out.println(kth(arr, 4));

    }

    // 12 23 34 54 65 76 87

    /**
     * 找出{@code arr}中第{@code k}小的元素
     * @param arr
     * @param k
     * @return
     */
    private static <T extends Comparable<T>> T kth(T[] arr, int k) {

        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            int p = partition(arr, low, high);
            if (p < k) {
                low = p + 1;
            } else if (p > k) {
                high = p - 1;
            } else {// p==k
                return arr[k];
            }
        }
        return arr[k];
    }

    private static <T extends Comparable<T>> void sort(T[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] arr, int low, int high) {

        if (high <= low) {
            return;
        }
        int p = partition(arr, low, high);
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    private static <T extends Comparable<T>> int partition(T[] arr, int low, int high) {

        T p = arr[low];
        while (low < high) {
            while (low < high && arr[high].compareTo(p) > 0) {
                high--;
            }
            if (low < high) {
                arr[low] = arr[high];
                low++;
            }
            while (low < high && arr[low].compareTo(p) < 0) {
                low++;
            }
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        arr[low] = p;
        return low;
    }
}
